package edu.cityu.cs.hk.datastructures;
import java.util.Comparator;

/**
  * Realization of an adaptable priority queue by means of a heap.
  * Much functionality is inherited.
  *
  * @author Eric Zamore
  * @see HeapPriorityQueue
  */

public class HeapAdaptablePriorityQueue extends HeapPriorityQueue
  implements AdaptablePriorityQueue {
  /** Creates an empty heap with a default comparator. */ 
  public HeapAdaptablePriorityQueue() { 
    super();
  }
  /** Creates an empty heap with the given comparator. */ 
  public HeapAdaptablePriorityQueue(Comparator comp) { 
    super(comp);
  }
  /** Inserts a key-value pair and returns the entry created. */
  public Entry insert (Object k, Object v) throws InvalidKeyException {
    checkKey(k);
    LocationAwareEntry entry = new LocationAwareEntry(k,v);
    Position z = T.add(entry);	// add entry to the tree
    entry.setLocation(z);	// make this entry location-aware
    upHeap(z);			// perform up-heap bubbling
    return entry;
  }
  /** Removes and returns the given entry from the heap. */
  public Entry remove(Entry entry) throws InvalidEntryException {
    LocationAwareEntry ee = checkEntry(entry);
    Position p = ee.location();
    if(size() == 1)
      return (Entry)T.remove();
    replaceEntry(p,(LocationAwareEntry)T.remove());
    upHeap(p);
    downHeap(p);
    ee.setLocation(null);
    return ee;
  }
  /** Replaces the key of the given entry. */
  public Object replaceKey(Entry entry, Object k) 
    throws InvalidEntryException 
  {
    checkKey(k);
    LocationAwareEntry ee = checkEntry(entry);
    Object oldKey = ee.setKey(k);
    upHeap(ee.location());
    downHeap(ee.location());
    return oldKey;
  }
  /** Replaces the value of the given entry. */
  public Object replaceValue(Entry e, Object value) 
    throws InvalidEntryException
  {
    LocationAwareEntry ee = checkEntry(e);
    return ee.setValue(value);
  }
  /** Swaps the elements of the two positions.  This method is called
   * when up-heaping and down-heaping. */
  protected void swapElements(Position u, Position v) {
    super.swapElements(u,v);	// swap the entries held by the positions
    getEntry(u).setLocation(u);	// swap the position references
    getEntry(v).setLocation(v);
  }

  /** Replaces the element of the given position with the given
   * location-aware entry. */
  protected Object replaceEntry(Position v, LocationAwareEntry e) {
    T.replace(v,e);		// replace the entry in the tree
    return e.setLocation(v);	// make the new entry aware of its position
  }
  /** Returns the entry stored at a heap node. */
  protected LocationAwareEntry getEntry (Position p) { 
    return (LocationAwareEntry) p.element(); 
  }
  
  /** Check whether a given entry is valid. */
  protected LocationAwareEntry checkEntry(Entry ent) 
    throws InvalidEntryException 
  {
    if(ent == null || !(ent instanceof LocationAwareEntry))
      throw new InvalidEntryException("Invalid entry");
    return (LocationAwareEntry)ent;
  }

  /** Inner class for a location-aware entry. */
  protected static class LocationAwareEntry extends MyEntry implements Entry {
    protected Position loc;
    public LocationAwareEntry(Object k, Object v) {
      super(k, v);
    }
    public LocationAwareEntry(Object k, Object v, Position pos) {
      super(k, v);
      loc = pos;
    }
    protected Position location() {
      return loc;
    }
    protected Position setLocation(Position pos) {
      Position oldPosition = location();
      loc = pos;
      return oldPosition;
    }
    protected Object setKey(Object k) {
      Object oldKey = key();
      key = k;
      return oldKey;
    }
    protected Object setValue(Object v) {
      Object oldValue = value();
      value = v;
      return oldValue;
    }
  }
}





